package BasicDataStructures;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class MyLinkedHashMap<K,V> {



    private static class Node<K,V> {
        K key;
        V val;
        Node<K,V> next,prev;

        Node(K key,V val) {
            this.key = key;
            this.val = val;
        }
    }

    private final Node<K,V> head,tail;

    //创建一个哈希表
    private final HashMap<K,Node<K,V>> map = new HashMap<>();

    //使用了虚拟头尾指针技巧
    public MyLinkedHashMap(){
        head = new Node<>(null,null);
        tail = new Node<>(null,null);
        head.next = tail;
        tail.prev = head;
    }

    //获取value
    public V get(K key) {
        Node<K,V> node = map.get(key);

        if (node != null) {
            return node.val;
        }

        return null;
    }

    public void put(K key,V val) {
        //检查map中是否有这个元素，没有的话同时插入链表和map
        if (!map.containsKey(key)){
            Node<K,V> node = new Node<>(key, val);
            map.put(key,node);
            addLastNode(node);
        }
        //map中已经有key
        //更新val值
        map.get(key).val = val;
    }

    public void remove(K key) {
        //检查map中是否有key
        //没有这个key，直接返回
        if (!map.containsKey(key)){
            return;
        }

        Node<K,V> node = map.get(key);
        //将<k,Node<k,v>>从map中摘除
        map.remove(key);
        //但是Node和其他Node的先后链接还存在
        //删除Node和其他node的联系
        removeNode(node);

    }

    private void addLastNode(Node<K,V> node) {
        Node<K,V> temp = tail.prev;

        node.next = tail;
        node.prev = temp;

        temp.next = node;
        tail.prev = node;
    }

    private void removeNode(Node<K,V> node) {
        Node<K,V> prev = node.prev;
        Node<K,V> next = node.next;

        prev.next = next;
        next.prev = prev;

        node.next = node.prev = null;
    }

    public List<K> keys() {
        List<K> keysList = new ArrayList<>();
        for (Node<K,V> p = head.next; p!=tail ; p = p.next) {
            keysList.add(p.key);
        }
        return keysList;
    }

    public static void main(String[] args) {
        MyLinkedHashMap<String, Integer> map = new MyLinkedHashMap<>();
        map.put("a", 1);
        map.put("b", 2);
        map.put("c", 3);
        map.put("d", 4);
        map.put("e", 5);

        System.out.println(map.keys()); // [a, b, c, d, e]
        map.remove("c");
        System.out.println(map.keys()); // [a, b, d, e]
    }
}
